package listnode;

public class _82_删除排序链表中的重复元素_2 {

    /**
     * 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。
     *
     * 示例 1:
     *
     * 输入: 1->2->3->3->4->4->5
     * 输出: 1->2->5
     * 示例 2:
     *
     * 输入: 1->1->1->2->3
     * 输出: 2->3
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates(ListNode head) {
        if (head==null) {
            return null;
        }
        ListNode result = new ListNode();
        ListNode tmp = result;
        boolean duplicate = false;
        ListNode beforeNode = head;
        head = head.next;

        while (head!=null){
            if (head.val == beforeNode.val) {
                duplicate = true;
            }else {
                if (!duplicate){
                    result.next = new ListNode(beforeNode.val);
                    result = result.next;
                }
                duplicate = false;
                beforeNode = head;
            }
            head = head.next;
        }

        if(!duplicate){
            result.next = new ListNode(beforeNode.val);
        }
        return tmp.next;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(3);
        ListNode n5 = new ListNode(4);
        ListNode n6 = new ListNode(4);
        ListNode n7 = new ListNode(5);
        n1.next=n2;
        n2.next=n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;
        n6.next=n7;
        ListNode node = deleteDuplicates1(n1);
    }

    /**
     * 思路：删除所有头部的重复节点，返回不重复的第一个节点。
     *
     * 1.特殊情况，头节点为null或头节点下一节点为null，直接返回头节点，这时不存在重复节点
     * 2.如果头节点与，头节点的下一节点值相等，跳过所有相等节点。递归调用函数判断最后一个跳过节点的后一节点。
     * 3.如果头节点与，头节点的下一节点值不等，递归调用函数判断头节点的后一节点。
     *
     * 作者：MapleStore
     * 链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/solution/javadi-gui-0ms-by-maplestore/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     * @param head
     * @return
     */
    public static ListNode deleteDuplicates1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            while (head.next != null && head.val == head.next.val) {
                head = head.next;
            }
            return deleteDuplicates1(head.next);
        } else {
            head.next = deleteDuplicates1(head.next);
            return head;
        }
    }

}
